[정렬] 병합정렬
정렬
| 정렬 알고리즘 | 정의 | 시간복잡도 |
|---|
| 삽입 | 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 | O(N) ~ O(N^2) |
| 버블 | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 | O(N^2) |
| 선택 | 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 | O(N^2) |
| 퀵 | pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 | O(NlogN) ~ O(N^2) |
| 힙 | 이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해정렬하는 방식 | O(NlogN) |
| 병합 | 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 | O(NlogN) + 추가적인 메모리 필요 |
| 기수 | 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 | O(N) + 추가적인 메모리 필요 |
병합정렬
병합정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
시간복잡도의 평균값은 O(NlogN) 이다
코딩테스트에의 정렬관련 문제에서 자주 등장 ( 특히 2개의 그룹을 병하는 원리는 꼭 숙지해야함 )
병합정렬 핵심 이론
| 순서 | 배열 | 배열 | 배열 | 배열 | 배열 | 배열 | 배열 | 배열 |
|---|
| 첫번째 | 42 (set1) | 32 (set2) | 24 (set3) | 60 (set4) | 15 (set5) | 5 (set6) | 90 (set7) | 45 (set8) |
| 두번째 | 32 (set1) | 42 (set1) | 24 (set2) | 60 (set2) | 5 (set3) | 15 (set3) | 45 (set4) | 90 (set4) |
| 세번째 | 24( set1) | 32 (set1) | 42 (set1) | 60 (set1) | 5 (set2) | 15 (set2) | 45 (set2) | 90 (set2) |
| 네번째 (정렬) | 5 | 15 | 24 | 32 | 42 | 45 | 60 | 90 |
- set를 작은 단위의 그룹으로 나눈다
- 2개의 그룹씩 병합하며 정렬을 진행한다
2개의 그룹 정렬하는 방법
투포인터를 사용하여, 정렬 진행
| 24 (set1) | 32 (set1) | 42 (set1) | 60 (set1) | 5 (set2) | 15 (set2) | 45 (set2) | 90 (set2) |
|---|
| (set1 인덱스) | -> 이동 | -> 이동 | -> 이동 | (set2 인덱스) | -> 이동 | -> 이동 | -> 이동 |
| (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) | (인덱스를 이동하면서, 더 작은 값을 먼저 배열에 저장) |
| 5 | 15 | 24 | 32 | 42 | 45 | 60 | 90 |
- index를 서로 움직이면서, 더 작은 값을 먼저 배열에 저장하는 구조 ( 투포인터를 이용한 정렬 )
병합 정렬 구현
- 과정)
- 첫번째 while문에서 왼쪽 혹은 오른쪽 그룹의 index 끝까지 도달하게 됨
- 나머지 while문에서 남은 수 들을 arr에 넣어주는 역할
- megerSort()
- startIndex ~ middleIndex / middleIndex + 1 ~ endIndex (2개의 그룹)
- arr : 메서드 종료 전에 2개의 그룹이 합쳐져서 정렬이 됨
- tmp : 2개의 그룹을 합치기 전의 배열 저장
public class App {
public static void main(String[] args) throws Exception {
int[] arr = {2,4,1,3,5,6};
mergeSort(arr, 0, arr.length - 1);
printArray(arr);
}
private static void mergeSort(int[] arr, int startIndex, int endIndex){
if (endIndex - startIndex < 1){
return;
}
int middleIndex =startIndex+ (endIndex -startIndex)/2;
mergeSort(arr, startIndex, middleIndex);
mergeSort(arr, middleIndex + 1, endIndex);
int[] tmp = new int[arr.length];
for(int i =startIndex; i<= endIndex; i++){
tmp[i] = arr[i];
}
int index1 = startIndex;
int index2 = middleIndex+1;
int sortIndex = startIndex;
while(index1 <= middleIndex && index2 <= endIndex){
if( tmp[index1] > tmp[index2] ){
arr[sortIndex] = tmp[index2];
index2++;
sortIndex++;
}else{
arr[sortIndex] = tmp[index1];
index1++;
sortIndex++;
}
}
while(index1 <= middleIndex){
arr[sortIndex] = tmp[index1];
sortIndex++;
index1++;
}
while(index2 <= endIndex){
arr[sortIndex] = tmp[index2];
sortIndex++;
index2++;
}
}
private static void printArray(int[] arr){
for (int i : arr) {
System.out.println(i);
}
}
}
관련 문서